O(NP) algorithm
用語メモ
このalgorithmではなく、編集距離で使われる一般的な用語だけど ある要素列を別の要素列に変換するための最短手順
最長共通部分列
考え方
$ D=\Delta+2p
$ D: 編集距離
$ \Delta: 二つの要素列の長さの差
一般的な解説
二つの要素列のうち、短い方を$ A、長い方を$ Bとする
$ Aから$ Bに変換するには、$ Aと$ Bの長さの差($ \Delta)だけ挿入したあと、$ Bと同じになるまで要素を置換(削除&挿入 x $ p回)すればいい
よって、編集距離は挿入(コスト1)と置換(コスト2)の合計値$ \Delta+2pとなる
これ以上編集距離を縮めることはできない
証明は論文読んだら書く
例
cosenseをhelpfeelに変換するには、少なくとも1文字追加して0~7文字挿入&削除する必要があるtakker.icon
これ以上追加操作を減らせないし、挿入＆削除操作の回数範囲を狭くすることもできない
この1が$ \Deltaに、0~7が$ pに相当する
References
この記事の$ V_D(k)が下のコードのfpに該当する
この記事知らなかった
ライセンスがよくわからない
$ k,x,yの意味を理解したい
code:mod.ts
/**
* The algorithm implemented here is based on "An O(NP) Sequence Comparison Algorithm"
* by described by Sun Wu, Udi Manber and Gene Myers */
type Position = {
x: number;
y: number;
};
export interface Change<T> {
value: T;
type: "add" | "delete" | "common";
}
export interface DiffResult<T> {
from: ArrayLike<T>;
to: ArrayLike<T>;
editDistance: number;
buildSES(): Generator<Change<T>, void, unknown>;
}
export const diff = <T>(
left: ArrayLike<T>,
right: ArrayLike<T>,
): DiffResult<T> => {
const reversed = left.length > right.length;
const a = reversed ? right : left;
const b = reversed ? left : right;
const offset = a.length + 1;
const MAXSIZE = a.length + b.length + 3;
pathは$ kからsnake()で計算した座標が入っているpathposの要素番号を取得する函数に相当するもの
pathposとpathで単方向リストを実現しているっぽい？ なぜそんなことをしているかはまだわからない
変更がたくさんあるとpathposの要素数が500とか600に膨れ上がる
code:mod.ts
const path = new Array<number>(MAXSIZE);
path.fill(-1);
const snake = (k: number, p: number, pp: number) => {
let y = Math.max(p, pp);
let x = y - k;
同じ値が入っている要素番号を計算する
code:mod.ts
while (x < a.length && y < b.length && ax === by) { ++x;
++y;
}
xはkとyから計算できるの($ x=y-k)で返さなくていい
code:mod.ts
return y;
};
編集距離を計算しつつ、辿った経路を記録する
code:mod.ts
const fp = new Array<number>(MAXSIZE);
fp.fill(-1);
let p = -1;
const delta = b.length - a.length;
do {
++p;
探索範囲は$ -p\le k\le\Delta+pで十分
それ以外の領域は編集距離$ Dが$ \Delta+2pを越えてしまうので、求める解が存在しない
配列の添え字に負の値は使えないので、offsetを足して正にしている
code:mod.ts
for (let k = -p; k <= delta - 1; ++k) {
}
for (let k = delta + p; k >= delta + 1; --k) {
}
$ f_p(\Delta)が$ Bの長さと同じになったら終了
code:mod.ts
最短経路の座標リストを作る
code:mod.ts
const epc = [] as Position[];
{
while (r !== -1) {
}
}
code:mod.ts
console.log({ path, pathpos, epc });
return {
from: left,
to: right,
editDistance: delta + p * 2,
code:mod.ts
buildSES: function* () {
let xIndex = 0;
let yIndex = 0;
for (const { x, y } of reverse(epc)) {
while (xIndex < x || yIndex < y) {
if (y - x > yIndex - xIndex) {
yield { value: byIndex, type: reversed ? "delete" : "add" }; ++yIndex;
} else if (y - x < yIndex - xIndex) {
yield { value: axIndex, type: reversed ? "add" : "delete" }; ++xIndex;
} else {
yield { value: axIndex, type: "common" }; ++xIndex;
++yIndex;
}
}
}
},
};
};
配列を逆順にiterateするhelper函数
code:mod.ts
function* reverse<T>(list: ArrayLike<T>): Generator<T, void, unknown> {
for (let i = list.length - 1; i >= 0; i--) {
}
}
表示用
code:cli.ts
import { diff } from "./mod.ts";
const { args, options } = await new Command()
.name("diff")
.version("0.1.0")
.description(
"O(NP) algorithmによる文字列差分表示のテストプログラム",
)
.arguments("<left> <right>")
.option("--vertical", "差分を縦に表示する")
.parse(Deno.args);
const left = String(args0); const right = String(args1); const { buildSES, from, to } = diff(left, right);
console.log(${from} → ${to});
if (options?.vertical) {
console.log(
type === "add"
? + ${value}
: type === "delete"
? - ${value}
: ${value}
).join("\n"),
);
} else {
let signs = "";
let str = "";
for (const {value, type} of buildSES()) {
str += value;
const half = value
switch (type) {
case "add":
signs += "+";
break;
case "delete":
signs += "-";
break;
default:
signs += " ";
break;
}
}
console.log(${signs}\n${str});
}
code:sh
code:log
{
path: [
-1, -1, -1, -1, -1, 6,
7, 8, 11, 10, 9, -1,
-1, -1, -1, -1
],
pathpos: [
],
epc: [
{ x: 6, y: 7 },
{ x: 6, y: 6 },
{ x: 4, y: 5 },
{ x: 4, y: 4 },
{ x: 0, y: 1 },
{ x: 0, y: 0 }
]
}
kitten → sitting
+ s
- k
i
t
t
+ i
- e
n
+ g